//给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历） 
//
// 
//
// 示例 1： 
//
// 
//输入：root = [3,9,20,null,null,15,7]
//输出：[[15,7],[9,20],[3]]
// 
//
// 示例 2： 
//
// 
//输入：root = [1]
//输出：[[1]]
// 
//
// 示例 3： 
//
// 
//输入：root = []
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 树中节点数目在范围 [0, 2000] 内 
// -1000 <= Node.val <= 1000 
// 
// Related Topics 树 广度优先搜索 二叉树 👍 621 👎 0


package com.cjl.leetcode.editor.cn;

import java.util.*;

/**
 * [P107]_二叉树的层序遍历 II
 * @author cjl
 * @date 2022-10-07 21:35:52
 */
public class P107_BinaryTreeLevelOrderTraversalIi{
      public static void main(String[] args) {
            //测试代码
           Solution solution = new P107_BinaryTreeLevelOrderTraversalIi().new Solution();
      }
      //力扣代码
      //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * 递归，
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(null == root){
            return new ArrayList<>();
        }
        List<List<Integer>> resList = new LinkedList<>();
        Deque<TreeNode> currDeque = new ArrayDeque<>();
        currDeque.addFirst(root);
        while (currDeque.size()> 0 ){
            int size = currDeque.size();
            List<Integer> tmpList = new ArrayList<>();
            for(int i = 0; i < size ;i ++){
                TreeNode treeNode = currDeque.pollLast();
                tmpList.add(treeNode.val);
                if(null != treeNode.left){
                    currDeque.addFirst(treeNode.left);
                }
                if(null != treeNode.right){
                    currDeque.addFirst(treeNode.right);
                }
            }
            resList.add(0,tmpList);
        }
        return resList;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

  }